#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstdint>
#include <cstdio>
#include <ctime>
#include <stack>
#include <cstring>
#include <sstream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

//step1: 如果当前节点存在左子节点，就入栈，直到没有左子节点，将其输出
//step2: 然后检查是否存在右子节点，如果没有就弹出栈顶元素，寻找右子节点
//step3: 如果找到了就重复step1，如果栈空了都没有找到，说明已经遍历完成
class Solution {
public:
    // vector<TreeNode*> test;
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> sta;
        vector<int> vec;
        TreeNode* node = root;
        while (node){
            while (node->left){
                sta.push(node);
                node = node->left;
            }
            vec.push_back(node->val);

            if (node->right){
                node = node->right;
            }else{
                while(1){
                    if (sta.empty()){
                        node = NULL; //end
                        break;
                    }else{
                        node = sta.top();
                        sta.pop();
                        vec.push_back(node->val);
                        if (node->right){
                            node = node->right;
                            break;
                        }
                    }
                }
            }
        }
        return vec;
    }
};

vector<string> split(const string& s, const string& seperator) {
    vector<string> result;
    unsigned int posBegin = 0;
    unsigned int posSeperator = s.find(seperator);

    while (posSeperator != s.npos) {
        result.push_back(s.substr(posBegin, posSeperator - posBegin));// 
        posBegin = posSeperator + seperator.size(); // 分隔符的下一个元素
        posSeperator = s.find(seperator, posBegin);
    }
    if (posBegin != s.length()) // 指向最后一个元素，加进来
        result.push_back(s.substr(posBegin));

    return result;
}

TreeNode* buildTree(string str)
{
    vector<string> vecStr;
    vecStr = split(str, ",");
    // int branch = 0;
    stack<TreeNode*> treeNode;
    TreeNode* node = NULL;
    int step = 0; //0-create left node, 1-create right node
    int flag = 0;

    for (int i = 0; i < vecStr.size(); i++){
        if (vecStr[i] != "null"){
            int value;
            stringstream stream(vecStr[i]);  
            stream >> value;  
            cout << vecStr[i] << " " << value << endl;
            if (!flag){
                node = new TreeNode(value);
                flag = 1;
                step = 0;
                treeNode.push(node);
            }
            if (step){
                node->right = new TreeNode(value);
                node = node->right;
                step = 0;
            }else{
                node->left = new TreeNode(value);
            }
        }else{
            if (node){
                step = 1;
            }else{
                break;
            }
        }
    }
    return NULL;
}

int main()
{
    Solution su;

    // buildTree("1,null,2,3");

    return 0;
}
